home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / os2 / pccts.zip / AST.C < prev    next >
C/C++ Source or Header  |  1992-12-08  |  6KB  |  236 lines
  1. /* Abstract syntax tree manipulation functions
  2.  *
  3.  * SOFTWARE RIGHTS
  4.  *
  5.  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  6.  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  7.  * company may do whatever they wish with source code distributed with
  8.  * PCCTS or the code generated by PCCTS, including the incorporation of
  9.  * PCCTS, or its output, into commerical software.
  10.  * 
  11.  * We encourage users to develop software with PCCTS.  However, we do ask
  12.  * that credit is given to us for developing PCCTS.  By "credit",
  13.  * we mean that if you incorporate our source code into one of your
  14.  * programs (commercial product, research project, or otherwise) that you
  15.  * acknowledge this fact somewhere in the documentation, research report,
  16.  * etc...  If you like PCCTS and have developed a nice tool with the
  17.  * output, please mention that you developed it using PCCTS.  In
  18.  * addition, we ask that this header remain intact in our source code.
  19.  * As long as these guidelines are kept, we expect to continue enhancing
  20.  * this system and expect to make other tools available as they are
  21.  * completed.
  22.  *
  23.  * ANTLR 1.06
  24.  * Terence Parr
  25.  * Purdue University
  26.  * 1989-1992
  27.  */
  28. #ifdef __STDC__
  29. #include <stdarg.h>
  30. #else
  31. #include <varargs.h>
  32. #endif
  33.  
  34. /* ensure that tree manipulation variables are current after a rule
  35.  * reference
  36.  */
  37. void
  38. zzlink(_root, _sibling, _tail)
  39. AST **_root, **_sibling, **_tail;
  40. {
  41.     if ( *_sibling == NULL ) return;
  42.     if ( *_root == NULL ) *_root = *_sibling;
  43.     else if ( *_root != *_sibling ) (*_root)->down = *_sibling;
  44.     if ( *_tail==NULL ) *_tail = *_sibling;
  45.     while ( (*_tail)->right != NULL ) *_tail = (*_tail)->right;
  46. }
  47.  
  48. AST *
  49. zzastnew()
  50. {
  51. #ifdef __STDC__
  52.     extern char *calloc(unsigned, unsigned);
  53. #else
  54.     extern char *calloc();
  55. #endif
  56.  
  57.     AST *p = (AST *) calloc(1, sizeof(AST));
  58.     if ( p == NULL ) fprintf(stderr,"%s(%d): cannot allocate AST node\n",__FILE__,__LINE__);
  59.     return p;
  60. }
  61.  
  62. /* add a child node to the current sibling list */
  63. void
  64. zzsubchild(_root, _sibling, _tail)
  65. AST **_root, **_sibling, **_tail;
  66. {
  67.     AST *n = zzastnew();
  68. #ifdef DEMAND_LOOK
  69.     zzcr_ast(n, &(zzaCur), LA(0), LATEXT(0));
  70. #else
  71.     zzcr_ast(n, &(zzaCur), LA(1), LATEXT(1));
  72. #endif
  73.     zzastPush( n );
  74.     if ( *_tail != NULL ) (*_tail)->right = n;
  75.     else {
  76.         *_sibling = n;
  77.         if ( *_root != NULL ) (*_root)->down = *_sibling;
  78.     }
  79.     *_tail = n;
  80.     if ( *_root == NULL ) *_root = *_sibling;
  81. }
  82.  
  83. /* make a new AST node.  Make the newly-created
  84.  * node the root for the current sibling list.  If a root node already
  85.  * exists, make the newly-created node the root of the current root.
  86.  */
  87. void
  88. zzsubroot(_root, _sibling, _tail)
  89. AST **_root, **_sibling, **_tail;
  90. {
  91.     AST *n = zzastnew();
  92. #ifdef DEMAND_LOOK
  93.     zzcr_ast(n, &(zzaCur), LA(0), LATEXT(0));
  94. #else
  95.     zzcr_ast(n, &(zzaCur), LA(1), LATEXT(1));
  96. #endif
  97.     zzastPush( n );
  98.     if ( *_root != NULL )
  99.         if ( (*_root)->down == *_sibling ) *_sibling = *_tail = *_root;
  100.     *_root = n;
  101.     (*_root)->down = *_sibling;
  102. }
  103.  
  104. /* Apply function to root then each sibling
  105.  * example: print tree in child-sibling LISP-format (AST has token field)
  106.  *
  107.  *    void show(tree)
  108.  *    AST *tree;
  109.  *    {
  110.  *        if ( tree == NULL ) return;
  111.  *        printf(" %s", zztokens[tree->token]);
  112.  *    }
  113.  *
  114.  *    void before() { printf(" ("); }
  115.  *    void after()  { printf(" )"); }
  116.  *
  117.  *    LISPdump() { zzpre_ast(tree, show, before, after); }
  118.  *
  119.  */
  120. void
  121. zzpre_ast(tree, func, before, after)
  122. AST *tree;
  123. void (*func)(),   /* apply this to each tree node */
  124.      (*before)(), /* apply this to root of subtree before preordering it */
  125.      (*after)();  /* apply this to root of subtree after preordering it */
  126. {
  127.     while ( tree!= NULL )
  128.     {
  129.         if ( tree->down != NULL ) (*before)(tree);
  130.         (*func)(tree);
  131.         zzpre_ast(tree->down, func, before, after);
  132.         if ( tree->down != NULL ) (*after)(tree);
  133.         tree = tree->right;
  134.     }
  135. }
  136.  
  137. /* free all AST nodes in tree; apply func to each before freeing */
  138. void
  139. zzfree_ast(tree)
  140. AST *tree;
  141. {
  142.     if ( tree == NULL ) return;
  143.     zzfree_ast( tree->down );
  144.     zzfree_ast( tree->right );
  145.     zztfree( tree );
  146. }
  147.  
  148. /* build a tree (root child1 child2 ... NULL)
  149.  * If root is NULL, simply make the children siblings and return ptr
  150.  * to 1st sibling (child1).  If root is not single node, return NULL.
  151.  *
  152.  * Siblings that are actually siblins lists themselves are handled
  153.  * correctly.  For example #( NULL, #( NULL, A, B, C), D) results
  154.  * in the tree ( NULL A B C D ).
  155.  *
  156.  * Requires at least two parameters with the last one being NULL.  If
  157.  * both are NULL, return NULL.
  158.  */
  159. #ifdef __STDC__
  160. AST *zztmake(AST *rt, ...)
  161. #else
  162. AST *zztmake(va_alist)
  163. va_dcl
  164. #endif
  165. {
  166.     va_list ap;
  167.     register AST *child, *sibling=NULL, *tail, *w;
  168.     AST *root;
  169.  
  170. #ifdef __STDC__
  171.     va_start(ap, rt);
  172.     root = rt;
  173. #else
  174.     va_start(ap);
  175.     root = va_arg(ap, AST *);
  176. #endif
  177.  
  178.     if ( root != NULL )
  179.         if ( root->down != NULL ) return NULL;
  180.     child = va_arg(ap, AST *);
  181.     while ( child != NULL )
  182.     {
  183.         for (w=child; w->right!=NULL; w=w->right) {;} /* find end of child */
  184.         if ( sibling == NULL ) {sibling = child; tail = w;}
  185.         else {tail->right = child; tail = w;}
  186.         child = va_arg(ap, AST *);
  187.     }
  188.     if ( root==NULL ) root = sibling;
  189.     else root->down = sibling;
  190.     va_end(ap);
  191.     return root;
  192. }
  193.  
  194. /* tree duplicate */
  195. AST *
  196. zzdup_ast(t)
  197. AST *t;
  198. {
  199.     AST *u;
  200.     
  201.     if ( t == NULL ) return NULL;
  202.     u = zzastnew();
  203.     *u = *t;
  204.     u->right = zzdup_ast(t->right);
  205.     u->down = zzdup_ast(t->down);
  206.     return u;
  207. }
  208.  
  209. void
  210. zztfree(t)
  211. AST *t;
  212. {
  213. #ifdef zzd_ast
  214.     zzd_ast( t );
  215. #endif
  216.     free( t );
  217. }
  218.  
  219. #ifdef zzAST_DOUBLE
  220. /*
  221.  * Set the 'up', and 'left' pointers of all nodes in 't'.
  222.  * USER MUST CREATE up, left FIELDS using AST_FIELDS macro.
  223.  * Initial call is double_link(your_tree, NULL, NULL).
  224.  */
  225. void
  226. zzdouble_link(t, left, up)
  227. AST *t, *left, *up;
  228. {
  229.     if ( t==NULL ) return;
  230.     t->left = left;
  231.     t->up = up;
  232.     zzdouble_link(t->down, NULL, t);
  233.     zzdouble_link(t->right, t, up);
  234. }
  235. #endif
  236.